It is well recognized that the construction of any building, machine or equipment, generally referred to as a project, requires the collective performance of a number of individual operations or tasks for successful completion. Resources are required, as example, personnel, trained to accomplish the task, capital equipment and other resources, supplies and component parts, which need to be procured or built. Each task requires a finite time, determined by past experience, for completion. And precedence must be followed, in that some tasks typically must be completed before other tasks in the project may begin.
Prudence requires planning and, particularly, formulation of a schedule that defines the who, when, where and the how that is necessary for completion of the project in an orderly and efficient manner. In earlier eras, the foreman or manufacturing engineer, possessed the experience, training and intellect to arrange the tasks required by the project in mind and specify which persons were to carry out the tasks, the resources and supplies required, and other necessary details. That person could also provide a reasonable estimate of the time of completion as allowed prediction of a delivery date.
As modern factory projects attained greater complexity, schedules required better definition and were more scientifically defined by persons, often now referred to as industrial engineers. With essentially pen, ink and calculator, such persons were able to search through the requirements and present the paper documents defining the tasks and the resources associated with them and to arrange the order of tasks for completion, creating time-lines of individual tasks and chronological order of the tasks commencement and completion, namely produce a project schedule. As projects became more complex still, those scheduling techniques often proved inefficient and, while less than perfect, necessarily sufficed until the advent of automated calculating machinery, such as the modern digital computer and the now familiar scheduling programs carried out by the computer.
In the modern competitive industrial world, however, all resources and personnel are held to a minimum and must be allocated. Little excess personnel or equipment is available to a manufacturer. Excess resources are expensive to maintain and, if carried idle by the manufacturer for too long, results ultimately in financial collapse attributed to inefficiency. Thus, the usefulness of a schedule as a useful industrial tool and the benefit of efficient scheduling to industrial craft is well understood.
In this endeavor the modern digital computer, more specifically, a programmed general purpose digital computer, plays an important role as a scheduler to expedite production of an acceptable schedule definition more quickly and efficiently than could be accomplished by human intellect alone. The computer is governed by a program, called software, and makes the necessary steps, called algorithms, set forth by the program. And those programs of interest here are those that deal with scheduling, hereinafter referred to as scheduling programs. In and of itself the digital computer is an instrument or tool for specifying not only the steps of the desired schedule, but also carries out the steps or method for attaining and defining those steps.
One known scheduling program used in the industry is called COMPASS, which is written in the well known ADA computer language or source code, as variously termed, and is used principally with workstation computers using the Unix operating system. A more recently introduced scheduling program is Microsoft Project which is written for operation on personal type computers, such as the Intel 486 and 586 processor based personal IBM type computers with Windows operating systems.
Scheduling is a difficult art. Mathematically the scheduling process is categorized as N.P.-Hard. This means that in order to determine an optimum schedule, one that accomplishes the project with available resources in a minimum amount of time to project completion, and which can be mathematically proven to be the optimum schedule, requires an unduly large amount of searching operations by the computer. That in turn requires computer time in such large amounts as to render those kinds of computerized scheduling programs impractical for industrial use.
To construct a modern aircraft involves many thousands of individual tasks, a vast number of technicians and assemblers, and a large amount of resources. To prepare a schedule for such a project would likely overwhelm the genius of any person working with pen, paper and calculator and would require an inordinate amount of time for one person or even a group of people to schedule to complete with minimal errors. One should not expect that the definition of a schedule to construct an aircraft should require preparation time that exceeds the construction time of an aircraft, disregarding the realism which necessitates redefining the schedule when tasks are not completed on time as originally planned, as for example due to acts of force majeure, such as electrical failure or flood.
As a consequence the scheduling programs implemented for industry are referred to as "Heuristic" in nature. That is, the algorithm that forms the essence of the scheduling program is based on a skilled person's intuition. Based on experience such programs are known to function to produce a good schedule, and/or improve an existing schedule. The logic as to why, the mathematical proof, however, is absent. The present invention is also heuristic in nature and the new algorithms presented are also based on intuition.
The duration between the start of the first scheduled project and the finish of the last scheduled task in a multiple task project is one measure of schedule "quality", often referred to as span time or cycle time. Another is the time required for the time to complete the process of formulating a schedule, that is, for the computer to execute the algorithms and process the entered task data to generate and display the schedule, often referred to as the "execution time".
Even Heuristic based scheduling programs are not created equal and vary widely in quality. Most computer assisted programs for producing good schedules suffer one of two basic flaws. Either they use simple methods that work quickly, but produce schedules with inferior "cycle time", or that use methods that produce schedules with good cycle time, but require excessive amounts of computer execution time. In short, the schedules produced takes too much time for project completion or the program takes too much time to formulate the schedule.
Some of these scheduling programs, such as one attributed to Gil Syswerda, provide an improved schedule, each time the program is run, continuing until a point of diminishing return is reached at which addotional improvement to the schedule is miniscule and does not justify further investment of computer execution time. The algorithm produces incremental improvement. The present algorithm is of like kind, producing incremental improvement each time the algorithm is applied to the most recently produced schedule.
An object of the present invention is to provide an improved scheduling method and apparatus and to improve upon existing scheduling methods and apparatus.
Another object of the invention is to provide an algorithm that may be added to existing scheduling programs for improving the quality of the formulated schedules.
An additional object of my invention is to provide an efficient method for defining a high quality schedule.
Still another object of the invention is to produce schedules for projects comprised of multiple tasks having minimal cycle time with only marginal increase in computer execution time.
And an ancillary object of the invention is to provide a novel scheduling algorithm that enhances existing scheduling programs.